package com.foxzzz.dynamic.programming;

// -
public class Solution121 {
    public static void main(String[] args) {
        System.out.println(new Solution121().maxProfit(new int[]{1,2,4}));
    }

    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
        int[] dp = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            int profit = 0;
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i]<prices[j]) {
                    profit = Math.max(prices[j]-prices[i],profit);
                }
            }

            dp[i]=Math.max(i-1<0?0:dp[i-1],profit);
        }
        return dp[prices.length-1];
    }
}
